package leetcode;

import util.LinkList;
import util.ListNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0023.java
 * @Author : WangRuoyu
 * @Date 2023/11/20 22:12
 */


public class Q0023 {
    /**
     * 堆排序
     **/
//    public ListNode mergeKLists(ListNode[] lists) {
//        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
//        for (ListNode node : lists) {
//            if (node != null) pq.add(node);
//        }
//        ListNode head = new ListNode(-1);
//        ListNode p = head;
//        while (!pq.isEmpty()) {
//            p.next = pq.poll();
//            p = p.next;
//            if (p.next != null) pq.add(p.next);
//        }
//        return head.next;
//    }

    /**
     * 分治 + 两个有序链表合并
     **/
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        mergeList(lists, 0, lists.length - 1);
        return lists[0];
    }

    private void mergeList(ListNode[] listNodes, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        mergeList(listNodes, l, mid);
        mergeList(listNodes, mid + 1, r);

        if (listNodes[l] == null) {
            listNodes[l] = listNodes[mid + 1];
            return;
        }
        if (listNodes[mid + 1] == null) {
            return;
        }

        if (listNodes[l].val > listNodes[mid + 1].val) {
            ListNode tmp = listNodes[l];
            listNodes[l] = listNodes[mid + 1];
            listNodes[mid + 1] = tmp;
        }
        ListNode p = listNodes[l];
        ListNode q = listNodes[mid + 1];
        ListNode pre = new ListNode(-1, p);

        while (p != null && q != null) {
            if (p.val <= q.val) {
                p = p.next;
                pre = pre.next;
                continue;
            }
            ListNode tmp = q.next;
            q.next = p;
            pre.next = q;
            pre = q;
            q = tmp;
        }

        if (q != null) pre.next = q;
    }

    public static void main(String[] args) {
        Q0023 sl = new Q0023();
        ListNode[] listNodes = new ListNode[2];
        ListNode node1 = LinkList.createList(new int[]{1, 3, 4});
        ListNode node2 = LinkList.createList(new int[]{2, 4, 6});
        listNodes[0] = node1;
        listNodes[1] = node2;
        LinkList.printList(sl.mergeKLists(listNodes));
    }
}


